class Solution {

    public int maxValue(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int height = grid.length, width = grid[0].length;
        for (int i = 1; i < height; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        for (int i = 1; i < width; i++) {
            grid[0][i] += grid[0][i - 1];
        }
        for (int i = 1; i < height; i++) {
            for (int j = 1; j < width; j++) {
                grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[height - 1][width - 1];
    }


    public static void main(String[] args) {
        int[][] arr = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };
        Solution s = new Solution();
        int ans = s.maxValue(arr);
        System.out.println(ans);
    }
}